public class LinkedListOJ {
    //1.删除链表中等于给定值 **val** 的所有节点。并统计。
    public ListNode removeElements(ListNode head, int val){
        if (head == null) return null;

        while (head.val == val){
            head = head.next;
            if (head == null) return null;
        }

        ListNode cur = head;
        ListNode prev = head;
        while (cur != null){
            if (cur.val == val){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        return head;
    }
    public int moveAllKey(ListNode head, int key){

        if (head == null) return 0;

        ListNode cur = head.next;
        ListNode prev = head;
        int count = 0;

        while (cur != null){
            if (cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
                count++;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }

        if (head.val == key){
            head = head.next;
            count = 1;
        }

        return count;
    }

    //2.反转一个单链表。
    public ListNode reverseList(ListNode head){
        if (head == null) return null;
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        head.next = null;
        return prev;
    }

    //3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
    //运用两次遍历，不够好
    public ListNode middleNode(ListNode head){
        if (head == null) return null;
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        cur = head;
        int a = count / 2;
        while(a != 0){
            cur = cur.next;
            a--;
        }
        return cur;
    }
    //只用一次遍历,快慢指针
    public ListNode middleNode1(ListNode head){
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //4.输入一个链表，输出该链表中倒数第k个结点。
    public ListNode FindKthToTail(ListNode head,int k){
        if (k < 0) return null;
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        cur = head;
        int a = count - k;
        if (a < 0) return null;
        while(a != 0){
            cur = cur.next;
            a--;
        }
        return cur;
    }
    //与第三题同理，只遍历一遍
    public ListNode FindKthToTail1(ListNode head,int k){
        if (head == null || k < 0) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (k - 1 != 0){
            fast = fast.next;
            if (fast == null){
                return null;//只有4个数，倒数第五个就不符合
            }
            k--;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (l1 != null && l2 != null){
            if (l1.val > l2.val){
                tmp.next = l2;
                tmp = l2;
                l2 = l2.next;
            }else {
                tmp.next = l1;
                tmp = l1;
                l1 = l1.next;
            }
        }
        //有其他链表没走完的情况，或者一开始就有空链表的情况
        if (l1 != null) {
            tmp.next = l1;
        }
        if (l2 != null){
            tmp.next = l2;
        }
        return newHead.next;
    }

    //6.以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
    public ListNode partition(ListNode pHead, int x){
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while (cur != null){
            if (cur.val < x){
                //第一次
                if (bs == null){
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if (as == null){
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //这里有问题
        //1.不是所有数都大于x
        //2.如果最后一个数小于x，那么倒数第二个节点要手动改为null
        if (be == null){
            return as;
        }
        if (as != null){
            ae.next = null;
        }
        be.next = as;
        return bs;
    }

    //7.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
    public ListNode deleteDuplication(ListNode head){
        //重复的元素不止一个，且重复的元素紧挨在一起
        if (head == null){
            return null;
        }
        ListNode cur = head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (cur != null){
            if (cur.next != null && cur.val == cur.next.val){//注意如果只有一个节点时，它的next为null
                while (cur.next != null && cur.val == cur.next.val){//如果最后一个节点值也是重复的，要结束
                    cur = cur.next;
                }
                //多走一步
                cur = cur.next;
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
        //注意&&和||区别，&&都要判断，||只需要判断一个，而且条件前后顺序要注意
    }

    //8.链表的回文结构。
    public boolean chkPalindrome(ListNode head){
        if (head == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        //走到中间位置反转
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curNext = cur.next;//curNext反复刷新，必须要在循环内
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        /*while (head != slow){
            if (head.val == slow.val){
                head = head.next;
                slow = slow.next;
                if (head.next == slow){
                    return true;
                }
            }else {
                return false;
            }
        }自己的写法，没问题，但比较复杂*/
        //头尾一起走，如果找到不同就false
        while(head != slow) {
            if(head.val != slow.val) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    //9.有两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点。没有交点，返回 null 。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headA == null){
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while (pl != null){
            lenA++;
            pl = pl.next;
        }
        //不能让pl走到末尾就再也用不了了
        pl = headA;
        while (ps != null){
            lenB++;
            ps = ps.next;
        }
        ps = headB;
        int len = lenA - lenB;
        if (len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        while (len != 0){
            pl = pl.next;
            len--;//别忘了
        }
        while (pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }

    //10.给定一个链表，判断链表中是否有环。
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        //如果不带环就退出了呀
        return false;
    }

    //11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回null
    public ListNode detectCycle(ListNode head){
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        //先判断是不是环，fast变成null就不是环，因为有可能fast和slow有可能都是null而相等
        if (fast == null || fast.next == null){
            return null;
        }
        //如何判断：一个节点在相遇处，一个节点在起点，他们一起走，第一次相遇点就是第一个节点
        fast = head;
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

}
